package problem4;

//4.寻找两个正序数组的中位数
//https://leetcode.cn/problems/median-of-two-sorted-arrays/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if(m > n) {
            return findMedianSortedArrays(B, A);
        }

        int l = 0, r = m;
        while(l <= r) {
            int i = (l + r) / 2;
            int j = (n + m + 1) / 2 - i;
            if(i > 0 && j != n && A[i - 1] > B[j]) {
                r = i - 1;
            }else if(i != m && j > 0 && A[i] < B[j-1]) {
                l = i + 1;
            }else {
                //和为奇数的情况
                int leftMax = 0;
                if(i == 0) leftMax = B[j-1];
                else if(j == 0) leftMax = A[i-1];
                else leftMax = Math.max(A[i-1], B[j-1]); 

                if((n + m) % 2 == 1) return leftMax;

                int rightMin = 0;
                if(i == m) rightMin = B[j];
                else if(j == n) rightMin = A[i];
                else rightMin = Math.min(A[i], B[j]);
                return (leftMax + rightMin) / 2.0;
            }
        }
        return -1;
    }
}

/*
        i
1 2 3 | 4 
4 5 | 6 7 8
      j    
           i
1 2 3 4 5 |
4 | 5 6 7 8 9
    j

*/